package leetcode.D800.T739;

import java.util.Deque;
import java.util.LinkedList;

class Solution {
    /*// 一刷
    public int[] dailyTemperatures(int[] T) {
        int[] result = new int[T.length];
        Deque<Integer> dq = new LinkedList<>();
        for(int i=T.length-1; i>=0; --i) {
            while(!dq.isEmpty() && T[dq.getLast()] <= T[i]) {
                dq.removeLast();
            }
            result[i] = dq.isEmpty() ? 0 : dq.getLast() - i;
            dq.addLast(i);
        }
        return result;
    }*/

    // 二刷
//    public int[] dailyTemperatures(int[] T) {
//        int[] result = new int[T.length];
//        Deque<Integer> dq = new LinkedList<>();
//        for(int i=T.length-1; i >= 0; --i) {
//            while(!dq.isEmpty() && T[dq.getLast()] <= T[i]) {
//                dq.removeLast();
//            }
//            result[i] = dq.isEmpty() ? 0 : dq.getLast() - i;
//            dq.addLast(i);
//        }
//        return result;
//    }

    // 三刷
    /*public int[] dailyTemperatures(int[] T) {
        int[] result = new int[T.length];
        Deque<Integer> dq = new LinkedList<>();
        for(int i=T.length-1; i>=0; --i) {
            while(!dq.isEmpty() && T[dq.getFirst()] <= T[i]) {
                dq.removeFirst();
            }
            result[i] = dq.isEmpty() ? 0 : dq.getFirst() - i;
            dq.addFirst(i);
        }
        return result;
    }*/

    // 四刷
    /*public int[] dailyTemperatures(int[] T) {
        Deque<Integer> dq = new LinkedList<>();
        int[] result = new int[T.length];
        for(int i=T.length-1; i>=0; --i) {
            while(!dq.isEmpty() && T[dq.getLast()] <= T[i]) {
                dq.removeLast();
            }
            result[i] = dq.isEmpty() ? 0 : dq.getLast() - i;
            dq.addLast(i);
        }
        return result;
    }*/

    // 五刷
    public int[] dailyTemperatures(int[] T) {
        Deque<Integer> dq = new LinkedList<>();
        int[] ans = new int[T.length];
        for (int i=T.length-1; i>=0; --i) {
            while (!dq.isEmpty() && T[dq.peek()] <= T[i])
                dq.pop();
            ans[i] = dq.isEmpty() ? 0 : dq.peek() - i;
            dq.push(i);
        }
        return ans;
    }
}
